package leetcode.code1079;

public class Solution {

	public int numTilePossibilities(String tiles) {
		char[] cs = tiles.toCharArray();
		int[] d = new int[26];
		int len = 0;
		for (int i = 0; i < cs.length; i++) {
			int index = cs[i] - 'A';
			if (d[index] == 0) {
				len++;
			}
			d[index]++;
		}
		int[] c = new int[len];
		for (int i = 0, j = 0; i < d.length; i++) {
			if (d[i] != 0) {
				c[j++] = d[i];
			}
		}
		return this.f(c, cs.length);
	}

	private int f(int[] c, int need) {
		if (need == 0) {
			return 0;
		}
		int ans = 0;
		for (int i = 0; i < c.length; i++) {
			if (c[i] != 0) {
				ans += 1;
				c[i]--;
				ans += this.f(c, need - 1);
				c[i]++;
			}
		}
		return ans;
	}

}
